Ch3 Solving Problem by Searching

Introduction

• problem-solving agent: 本單元討論該agent
  • 是一種goal-based agent (考慮未來行動 以及結果的可行性)
• limit: 考慮簡單的PEAS => 解答是一串固定的行動

Problem-Solving Agent

• search: 找到能達成目標的一串行動

• 例題

Well-Defined Problems and Solutions

• 定義問題的五個組件
  • Initial state
  • action
  • transition model
  • goal test: 是否達成目標的測試
  • path cost: 路徑花費

Formulating Problems

• 8拼圖問題

• 8皇后問題

Real-World Problems

Searching for Solutions

Infrastructure for Search Algorithms

Measuring Problem-Solving Performance

• Completeness: 當存在解的時候，算法是否保證找到一組解

Uninformed Search Strategies

• Uninformed search: 無資訊搜尋
  • 不知道節點額外資訊，只能確定是否為goal state
  • 關注的是節點展開順序
• informed search: 有資訊搜尋
  • 同義: heuristic search 啟發式搜尋

• BFS
• node generate num.
  • 
• measure
  • 

• 均值成本搜索(AI) or Dijkstra’s algorithm(Theoretical CS)
  • 生成節點的時候不做goal test, expand node 的時後才做 (延遲)
  • 每一步擴展 path cost 最低的點
• measure
  • 
  • 指導原則是 path cost, 而非depth
  • 當所有 step costs 相同 則相當於BFS

• DFS
• measure
  • 
    • 可能超耗時間
  • 
    • 節省儲存空間
• 
  • 根據我們對問題的瞭解 可以限制深度進行DFS
• 
  • 慢慢增加深度限制 得到兼顧空間、時間、completeness、optimal 的方法
  • 
    • 最推薦的方式
  • 
    • 為何這不是大問題： 在搜尋樹中，隨著深度增加，每層的分支節點數目（即分支因子，branching factor）通常以指數增長。因此：
      • 上層節點數量較少：相比樹的底層節點，樹的上層節點數目是極少的。底層節點佔主要計算量：樹中大部分節點集中於最深的那一層。因此，即便多次生成上層節點，對總計算成本影響不大。

• 雙向搜尋
• 
  • 困難點是從goal 向後搜尋

Informed (Heuristic) Search Strategies

• 使用專屬於該問題的資訊來解決問題

• 貪心優先搜尋
  • 拿各城市到goal city 的直線距離來當作資訊
• 
  • 未必是最佳解
• 
  • 在有限狀態空間是completemess 無限狀態空間則否

• A星算法
  • 使用到當前節點的 g(n) path cost
  • h(n) 當前節點到目標節點的estimated cost
• 
  • 有條件的optimality
  • 不高估實現目標的成本
• 
  • estimated costs 的三角不等式